#include <suif_copyright.h>
#include <stdio.h>
#include <stdlib.h>
#include <simple.h>
#include "print.h"
#include "bitvector.h"


struct _basic_block_node;
struct _block_ptr;

typedef struct _instr_node {
	int number;
	simple_instr * instr;
	struct _instr_node * next;
	struct _instr_node * previous;
	struct _basic_block_node * block;
	bit_vector * defs;
} instr_node; 

typedef struct _basic_block_node {
	int number;
	int total_instrs;
	int total_predecessors;
	int total_successors;
	instr_node * start;
	instr_node * end;
	struct _basic_block_node * next;
	struct _basic_block_node * previous;
	bit_vector * dom;
	bit_vector * pdom;
	bit_vector * idom;
	struct _block_ptr * predecessor;
	struct _block_ptr * successor;

	bit_vector *lvout;                  	// set of live variables at the beginning of b
   	bit_vector *lvin;                   	// set of live variables at the end of b
   	bit_vector *def;			// set of defined variables
   	bit_vector *use;			// set of used variables
	bit_vector *eval_expr;			// set of evaluated expression
	bit_vector *kill_expr;			// set of killed expression
	bit_vector *aein;			// set of available expressions at the beginning of b
	bit_vector *aeout; 			// set of available expressions at the end of b
	bit_vector *ac_copy;		// set of copy instruction (u = v)
	bit_vector *ac_kill;		// set of copy instructions that are killed by b
	bit_vector *acin;			// set of copy instructions available at the beginning of b
	bit_vector *acout;		// set of copy instructions available at the end of b
    bit_vector *rdin;
    bit_vector *rdout;
    bit_vector *rdkill;
    bit_vector *rdgen;
} basic_block_node; 

typedef struct _block_ptr {
	basic_block_node * block;
	struct _block_ptr * next;
} block_ptr;

typedef struct _instr_ptr {
    int number;
    instr_node * instr;
    struct _instr_ptr * next;
} instr_ptr;

typedef struct _loop_block {
	block_ptr * head;
	block_ptr * tail;
	struct _loop_block * next;
	bit_vector * nodes;
    bit_vector * invariant_instrs;
    instr_node * preheader;
} loop_block;

typedef struct _reg {
    int number;
    simple_reg * r;
    struct _reg * next;
    struct _reg * prev;
} reg;

typedef struct _constant_reg {
    simple_reg * r;
    simple_immed value;
    instr_node * instr;
    struct _constant_reg * next;
    struct _constant_reg * prev;
} constant_reg;


typedef struct _expression {
	int number;
	instr_node * instr;
	simple_reg * r1;
	simple_reg * r2;
	simple_reg * dest;
	struct _expression * next;
	struct _expression * prev;
} expression;

// function declarations
void print_instrs(instr_node *);
void print_cfg(basic_block_node *, int);
void print_dom(basic_block_node *, int);
void print_idom(basic_block_node *, char *, int);
void print_natural_loops(loop_block *, int);
void insert_block_ptr(block_ptr **, basic_block_node *);
int number_instrs(instr_node **, simple_instr *);
int find_basic_block(basic_block_node **, instr_node *);
void find_predecessors(basic_block_node *);
void find_dominators(basic_block_node *, int);
void find_idominators(basic_block_node *, int);
void free_cfg(basic_block_node *);
int check_for_same_header(instr_node *, simple_instr *);
void find_loops(basic_block_node *, simple_instr **, instr_node **);
void print_block_ptr(block_ptr *);
void insert_loop_block(loop_block **, loop_block *);
loop_block * find_same_header(loop_block *, basic_block_node *);
void insert_on_stack(block_ptr **, basic_block_node *);
block_ptr * pop(block_ptr **);
int find_loop_info(basic_block_node *, loop_block **, int);

// assignment 3
int find_variables(instr_node *, reg **);
void print_variables(reg *, char *, int);
void lv_init(basic_block_node * block_head, int size, reg * reglist);
void print_def_set(basic_block_node * block_head, char * proc_name, int totalblocks);
void print_use_set(basic_block_node * block_head, char * proc_name, int totalblocks);

typedef int (*MeetOpFunc) (basic_block_node * blocks);
typedef int (*TransferFunc) (basic_block_node * blocks);
int lv_transferfunc(basic_block_node * block);
int lv_meet(basic_block_node * block);
int dfa_start(basic_block_node * block, MeetOpFunc meet_op, TransferFunc transfer_func, block_ptr ** stack, int dir);
block_ptr * find_in_stack(block_ptr * stack, basic_block_node * block);
void print_lvout(basic_block_node * block_head, char * proc_name, int totalblocks);

// assignment 4
int find_expressions(instr_node *, expression **);
void print_expressions(expression *, char *, int);
void expr_init(basic_block_node *, int, expression *);
void print_eval_expr(basic_block_node *, char *, int);
void print_kill_expr(basic_block_node *, char *, int);
int ae_transferfunc(basic_block_node *);
int ae_meet(basic_block_node *);
void print_aeout(basic_block_node *, char *, int);


// assignment 5
typedef struct _induction_var {
    simple_reg * v;
    simple_immed c;
    simple_op op;
    struct _induction_var * next;
} induction_var;

typedef struct _label_node {
    simple_sym * l;
    struct _label_node * next;
} label_node;

typedef struct _rdef_node {
    simple_reg * r;
    instr_ptr * instr;
    struct _rdef_node * next;
} rdef_node;


void runOptimizer(loop_block * loops);
int do_loop_invariant_code_motion(loop_block * loops, basic_block_node ** block_head, instr_node ** instr_head);
int optimize_a_loop(loop_block * loop, basic_block_node *, instr_node *);
void do_optional();
void do_copy_propagation(basic_block_node **, instr_node **, simple_instr *, int *, int *);
int find_copy_expressions(instr_ptr ** copy_instrs, instr_node * instrs);
void free_instr_ptr(instr_ptr * copy_instrs);
void print_copy_expr(basic_block_node * block_head);
void eval_copy_and_kill_sets(basic_block_node * block_head, instr_ptr * copy_instrs, int totalcopyinstrs);
int do_constant_folding(basic_block_node *);
void print_blocks(basic_block_node * block_head);
void do_dead_code_elimination(basic_block_node * block_head, instr_node * instr_head, int, int);